//给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
//
// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
//
//
//
// 示例1：
//
//
//
//
//输入：l1 = [7,2,4,3], l2 = [5,6,4]
//输出：[7,8,0,7]
//
//
// 示例2：
//
//
//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[8,0,7]
//
//
// 示例3：
//
//
//输入：l1 = [0], l2 = [0]
//输出：[0]
//
//
//
//
// 提示：
//
//
// 链表的长度范围为 [1, 100]
// 0 <= node.val <= 9
// 输入数据保证链表代表的数字无前导 0
//
//
//
//
// 进阶：如果输入链表不能翻转该如何解决？
//
// Related Topics 栈 链表 数学 👍 710 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
package main

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var s1 []*ListNode
	var s2 []*ListNode
	for l1 != nil {
		s1 = append(s1, l1)
		l1 = l1.Next
	}

	for l2 != nil {
		s2 = append(s2, l2)
		l2 = l2.Next
	}

	dn := &ListNode{}
	var carry int
	for {
		if len(s1) == 0 && len(s2) == 0 && carry == 0 {
			break
		}

		sum := carry
		if len(s1) != 0 {
			sum += s1[len(s1)-1].Val
			s1 = s1[:len(s1)-1]
		}

		if len(s2) != 0 {
			sum += s2[len(s2)-1].Val
			s2 = s2[:len(s2)-1]
		}

		node := &ListNode{Val: sum % 10, Next: dn.Next}
		dn.Next = node
		carry = sum / 10
	}
	return dn.Next
}

// leetcode submit region end(Prohibit modification and deletion)
